package com.atguigui.leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 522.最长特殊序列 II
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/6/27 9:16
 */
public class P522LongestUncommonSubsequenceIi {
    public static void main(String[] args) {
        Solution solution = new P522LongestUncommonSubsequenceIi().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /**
         * 找数组中，最长的孤儿，找出没有爹的字母
         *
         * @param strs
         * @return
         */
        public int findLUSlength(String[] strs) {

            // 先按长度排个序，长的在前面
            Arrays.sort(strs, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o2.length() - o1.length();
                }
            });


            int n = strs.length;
            boolean find = false;
            int len = strs[0].length();
            for (int i = 0; i < n; i++) {
                //
                String str1 = strs[i];
                len = str1.length();
                boolean special = true;
                for (int j = 0; j < n; j++) {
                    String str2 = strs[j];
                    if (i == j) {
                        continue;
                    }
                    // 如果父字母的长度小于儿子的长度直接跳出
                    if (str2.length() < len) {
                        break;
                    }
                    // 儿子的字母长度小于等于父字母的长度
                    if (judge(strs[i], strs[j])) {
                        // 匹配中一个就可以跳出
                        special = false;
                        break;
                    }

                }
                // 当全部遍历完找到的第一个str2不包含其余strs中所有字母则为最长的
                if (special) {
                    find = true;
                    break;
                }
            }

            return find ? len : -1;
        }

        /**
         * 判断父字母中是否有儿子字母
         *
         * @param str1 儿子
         * @param str2 父
         * @return true: str2中包含str1中的全部字母
         * false: str2中不包含str1中的全部字母
         */
        private boolean judge(String str1, String str2) {
            if (str1.length() == str2.length()) {
                return str1.equals(str2);
            }
            int i = 0, j = 0;
            // 双指针循环遍历2个字母
            while (i < str1.length() && j < str2.length()) {
                // 只要找出儿子字母中一个字母父字母中没有的，就会返回false
                if (str1.charAt(i) == str2.charAt(j)) {
                    i++;
                }
                j++;
            }

            // 等于就代表儿子字母中父字母中全都有
            return i == str1.length();
        }
    }
}
